/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package dungeonsolver.controller.algorithm;

import dungeonsolver.helper.Utility;
import dungeonsolver.model.Labyrinth;
import java.awt.Point;
import java.util.Vector;

/**
 *
 * @author LegACy
 */
public class AlgorithmGreedy implements IAlgorithm {

	public Point[] getPath(Labyrinth labyrinth, Point from, Point to) {
		//Check
		if (labyrinth == null || from.equals(to)) return new Point[0];

		//Create visited map
		boolean[][] Map = labyrinth.getVisitMap();

		//Create variables
		Point Current		= new Point(from);
		Vector<Point> Path	= new Vector<Point>();
		Vector<Point> Fork	= new Vector<Point>();

		//While not destination
		while (Current != null && (Current.x != to.x || Current.y != to.y)) {
			//Prepare log
			String Log = "Arrived at [" + Current.x + "," + Current.y + "]... ";
			
			//Set current position as visited
			Map[Current.x][Current.y] = true;

			//Get neighbors
			int ValidNeighbor = 0;
			Point[] Neighbors = labyrinth.getNeighbors(Current);
			for (int i = 0; i < Neighbors.length; i++) if (!Map[Neighbors[i].x][Neighbors[i].y]) ValidNeighbor++;
			if (ValidNeighbor > 1) {
				Fork.add(Current);
				Log += "Fork encountered.";
				Utility.instance().addLog(Log);
				Log = "";
			}

			//For each neigbor
			int i		= 0;
			Point Next	= null;
			while (i < Neighbors.length) {
				//If not visited yet
				if (!Map[Neighbors[i].x][Neighbors[i].y]) {
					//if no next, take it, otherwise
					if (Next == null) Next = Neighbors[i];
					else {
						//Compare distance between tile
						Utility.instance().addLog("Comparing distance between paths...");
						if (Utility.instance().isPointACloserThanB(Current, Neighbors[i], Next))
							Next = Neighbors[i];
					}
				}

				//Next neighbor
				i++;
			}

			//If no next tile
			if (Next == null) {
				//Log
				Log += "Dead end encountered, returning to last fork. ";

				//If fork exist
				if (!Fork.isEmpty()) {
					//Return to last fork
					Next = Fork.lastElement();
					Fork.remove(Next);

					//Remove paths
					while (Path.size() > 0 && !Path.lastElement().equals(Next)) Path.removeElementAt(Path.size() - 1);
				} else Path.removeAllElements();
			} else Path.add(Next);

			//Set as current
			Current = Next;

			//Add log
			if (!Log.equals("")) Utility.instance().addLog(Log);
		}

		//Log
		Utility.instance().addLog("Arrived at [" + Current.x + "," + Current.y + "]... Destination encountered.");

		//Create array
		Point[] PathArray = new Point[Path.size()];
		for (int i = 0; i < PathArray.length; i++) PathArray[i] = Path.elementAt(i);

		//Return path
		return PathArray;
	}
}
